// 归并排序 - 先把左边数组排好序，再把右边数组排好序，然后把两边数组合并

// 归并数组的框架：
// 定义：排序 nums[lo..hi]
void sort(int* nums, int lo, int hi)
{
	if(lo == hi)
		return;

	int mid = (lo + hi) / 2;

	// 利用定义，排序nums[lo..mid]
	sort(nums, lo, mid);

	// 利用定义，排序nums[mid+1, hi]
	sort(nums, mid+1, hi);
}

// 将有序数组nums[lo..mid]和有序数组nums[mid+1, hi]合并为有序数组[lo..hi]
void merge(int* nums, int lo, int mid, int hi);

// 上面的代码跟二叉树的后序遍历很像：
void traverse(TreeNode root)
{
	if(root == nullptr)
		return;

	traverse(root.left);
	traverse(root.right);

	// 后序位置
	print(root.val);
}

// 再联想一下求二叉树的最大深度代码：
int maxDepth(TreeNode root)
{
	if(root == nullptr)
		return 0;

	// 利用定义，计算左右子树的最大深度
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);

	// 整棵树的最大深度等于左右子树的最大深度加上根节点自己
	int res = max(leftMax, rightMax) + 1;

	return res;
}


// 归并排序的过程可以在逻辑上抽象成一棵二叉树，树上的每个节点的值可以认为是
// nums[lo..hi], 叶子节点的值就是数组中的单个元素
// 然后在每个节点的后序位置（左右子节点已经被排好序了）的时候执行merge函数，合并// 两个子节点上的子数组



// 归并算法模版：
class Merge
{
	// 用于辅助合并有序数组
	private static int[] temp;

	public static void sort(int[] nums)
	{
		// 先给辅助数组开辟内存空间
		temp = new int[nums.length];
		
		// 排序整个数组（原地修改）
		sort(nums, 0, nums.length - 1);
	}

	// 定义：将子数组nums[lo..hi]进行排序
	private static void sort(int[] nums, int lo, int hi)
	{
		if(lo == hi) // 单个元素不用排序
			return;

		// 为了防止溢出
		int mid = lo + (hi - lo) / 2;

		// 先把左半部分数组nums[lo..mid]排序
		sort(nums, lo, mid);

		// 再把右半部分数组nums[mid+1, hi]排序
		sort(nums, mid+1, hi);

		// 将两部分有序数组合并成一个有序数组
		merge(nums, lo, mid, hi);
	}

	// 将nums[lo..mid]和nums[mid+1..hi]这两个有序数组合并成一个有序数组
	private static void merge(int[] nums, int lo, int mid, int hi)
	{
		// 先把nums[lo..hi]复制到辅助数组中以便合并后的结果能够直接存入nums
		for(int i = lo; i <= hi; i++)
			temp[i] = nums[i];

		// 数组双指针技巧，合并两个有序数组
		int i = lo, j = mid + 1;
		for(int p = lo; p <= hi; p++)
		{
			if(i == mid + 1)
				// 左半边数组已全部被合并
				nums[p] = temp[j++];
			else if(j == hi + 1)
				// 右半边数组已全部被合并
				nums[p] = temp[i++];
			else if(temp[i] > temp[j])
				nums[p] = temp[j++];
			else 
				nums[p] = temp[i++];
		}
	}
};


// 归并排序解题框架：
class Merge
{
	// 用于辅助合并数组
	private static int[] temp;

	public static void sort(int[] nums)
	{
		// 先给辅助数组开辟内存空间
		temp = new int[nums.length];

		// 排序整个数组，原地修改
		sort(nums, 0, nums.length - 1);
	}

	// 定义：将子数组nums[lo..hi]进行排序
	private static void sort(int[] nums, int lo, int hi)
	{
		if(lo == hi) // 单个元素不排序
			return;

		// 为了防止溢出
		int mid = lo + (hi - lo) / 2;

		// 先对左半部分数组nums[lo..mid]排序
		sort(nums, lo, mid);

		// 再对右半部分数组nums[mid+1..hi]排序
		sort(nums, mid + 1, hi);

		// 将两部分有序数组合并成一个有序数组
		merge(nums, lo, mid, hi);
	}

	// 将nums[lo..mid]和nums[mid+1..hi]这两个有序数组合并成一个有序数组
	private static void merge(int[] nums, int lo, int mid, int hi)
	{
		// 先把nums[lo..hi]复制到辅助数组中
		// 以便合并后的结果能够直接存入nums中
		for(int i = lo; i <= hi; i++)
			temp[i] = nums[i];

		// 数组双指针技巧，合并两个有序数组
		int i = lo, j = mid + 1;

		for(int p = lo; p <= hi; p++)
		{
			if(i == mid+1)
				// 左半边数组已全部合并
				nums[p] = temp[j++];
			else if(j == hi+1)
				// 右半边数组已全部合并
				nums[p] = temp[i++];
			else if(temp[i] > temp[j])
				nums[p] = temp[j++];
			else 
				nums[p] = temp[i++];
			
		}
	}
};


class Solution {
public:

    // 定义辅助数组
    vector<int> temp;

    vector<int> sortArray(vector<int>& nums) 
    {
        // 为辅助数组开空间
        temp.resize(nums.size());

        sort(nums, 0, nums.size() - 1);

        return nums;
    }

    void sort(vector<int>& nums, int lo, int hi)
    {
        if(lo == hi) // 只有一个元素，不用排序
            return;

        // 防止整数溢出
        int mid = lo + (hi - lo) / 2;

        // 先对左半部分数组进行排序
        sort(nums, lo, mid);

        // 再对右半部分数组进行排序
        sort(nums, mid + 1, hi);

        // 然后合并排好序的数组的左右部分
        merge(nums, lo, mid, hi);
    }

    void merge(vector<int>& nums, int lo, int mid, int hi)
    {
        // 将nums数组中的值复制到temp数组中
        for(int i = lo; i <= hi; i++)
            temp[i] = nums[i];

        int i = lo, j = mid + 1;

        // 双指针技巧，合并两个有序数组
        for(int p = lo; p <= hi; p++)
        {
            if(i == mid + 1) // 左半部分合并好了
                nums[p] = temp[j++];
            else if(j == hi + 1) // 右半部分合并好了
                nums[p] = temp[i++];
            else if(temp[i] > temp[j])
                nums[p] = temp[j++];
            else 
                nums[p] = temp[i++];
        }
    }
};


// 快速排序解题框架：
void sort(int[] nums, int lo, int hi)
{
	if(lo >= hi)
		return;

	// 对nums[lo..hi]进行切分
	// 使得nums[lo..p-1] <= nums[p] <= nums[p+1..hi]
	int p = partition(nums, lo, hi);

	// 对左右子数组进行切分
	sort(nums, lo, p - 1);

	sort(nums, p + 1, hi);
}

// 其实快速排序就是二叉树的前序遍历
void traverse(TreeNode root)
{
	if(root == nullptr)
		return;

	// 前序位置
	print(root.val);

	traverse(root.left);

	traverse(root.right);
}


// 归并排序是先把左半边数组排好序，再把右半边数组排好序，然后把两边数组合并
// 快速排序是先将一个元素排好序，然后再把剩下的元素排好序

// 快速排序的核心无非就是partition函数，partition函数的作用是在nums[lo..hi]中寻找一个切分点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p],且nums[p+1..hi]都大于nums[p]

// 一个元素左边的元素都比它小，右边的元素都比它大，也就是说这个元素被放到了正确的位置上了

// 所以partition函数的作用就是把nums[p]这个元素排好序，然后再把剩下的元素排好序就行了


// 快速排序的代码实现
class Quick
{
	public static void sort(int[] nums)
	{
		// 为了避免出现耗时的极端情况，先随机打乱
		shuffle(nums);

		// 排序整个数组，原地修改
		sort(nums, 0, nums.length - 1);
	}

	// 洗牌算法，将输入的数组随机打乱
	private static void shuffle(int[] nums)
	{
		Random rand = new Random();

		int n = nums.length;

		for(int i = 0; i < n; i++)
		{
			// 生成[i, n-1]的随机数
			int r = i + rand.nextInt(n - 1);
			swap(nums, i, r);
		}
	}

	// 原地交换数组中的两个元素
	private static void swap(int[] nums, int i, int j)
	{
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
	
	private static void sort(int[] nums, int lo, int hi)
	{
		if(lo >= hi)
			return;

		// 对nums[lo..hi]进行切分
		// 使得nums[lo..p-1] <= nums[p] <= nums[p+1..hi]
		int p = partition(nums, lo, hi);

		sort(nums, lo, p - 1);

		sort(nums, p + 1, hi);
	}

	// 对nums[lo..hi]进行切分
	private static int partition(int[] nums, int lo, int hi)
	{
		int pivot =nums[lo];

		// 关于区间的边界控制需要格外小心，稍有不慎就会出错
		// 我这里把i,j定义为开区间，同时定义：
		// [lo,i) <= pivot; (j,hi] > pivot
		// 之后都要正确维护这个边界区间的定义
		int i = lo + 1, j = hi;

		// 当i>j时结束循环,以保证区间[lo,hi]都被覆盖
		while(i <= j)
		{
			while(i < hi && nums[i] <= pivot)
				i++; // 此时while循环结束恰好nums[i] > pivot
			while(j > lo && nums[j] > pivot)
				j--; // 此时while循环结束恰好nums[j] <= pivot
			
			if(i >= j)
				break;

			// 此时[lo,i) <= pivot && (j, hi] > pivot
			// 交换nums[j]和nums[i]
			swap(nums,i,j);
			// 此时[lo,i] <= pivot && [j,hi] > pivot 
		}

		// 最后将pivot放大合适的位置，即pivot左边元素较小，右边元素较大
		swap(nums, lo, j);
		return j;
	}
};


}
class Solution {
public:

    // 定义辅助数组
    vector<int> temp;

    vector<int> sortArray(vector<int>& nums) 
    {
        temp.resize(nums.size());

        sort(nums, 0, nums.size() - 1);

        return nums;
    }

    void sort(vector<int>& nums, int left, int right)
    {
        if(left >= right) // 只有一个元素时不用排序
            return;

        int mid = left + (right - left) / 2;

        sort(nums, left, mid);

        sort(nums, mid + 1, right);

        merge(nums, left, mid, right);
    }

    void merge(vector<int>& nums, int left, int mid, int right)
    {
        for(int i = left; i <= right; i++)
        {
            temp[i] = nums[i];
        }

        int i = left, j = mid + 1;

        for(int p = left; p <= right; p++)
        {
            if(i == mid + 1) // 左半部分排好序了
                nums[p] = temp[j++];
            else if(j == right + 1) // 右半部分排好序了
                nums[p] = temp[i++];
            else if(temp[i] > temp[j])
                nums[p] = temp[j++];
            else 
                nums[p] = temp[i++];
        }
    }
};

// 快速排序代码框架：
void QuickSort(int* a, int begin, int end)
{
	if(begin >= end) // 当一个数据或者序列不存在时，不需要进行操作
		return;

	int left = begin; // L
	int right = end; // R
	int keyi = begin; // key的下标

	while(left < right)
	{
		// 注意right先走,找小
		while(left < right && a[right] >= a[keyi]
			right--;
		// left再走，找大
		while(left < right && a[left] <= a[keyi])
			left++;

		if(left < right) // 交换left和right的值
			Swap(a[left], a[right]);
	}

	int meeti = left; // L和R的相遇点

	Swap(a[keyi], a[meeti]);

	QuickSort(a, beign, meeti - 1);
	QuickSort(a, meeti, end);
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>

using namespace std;


void PrintArray(int* array, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << array[i] << " ";
    }

    cout << endl;
}



// void _MergeSort(int* a, int left, int right, int* tmp)
// {
//     if(left >= right)
//     {
//         return;
//     }

//     int mid = left + (right - left) / 2;

//     // [left, mid] [mid + 1. right] - 分割
//     _MergeSort(a, left, mid, tmp);
//     _MergeSort(a, mid + 1, right, tmp);

//     // [left, mid] [mid + 1, right] - 归并
//     int begin1 = left, end1 = mid;
//     int begin2 = mid + 1, end2 = right;
//     int index = left;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++]; 
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
// }


// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);
//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, end] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp数组中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid][mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp数组中的数据拷贝回原数组
//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }


// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if(begin >= end)
    {
        return;
    }

    int mid = begin + (end - begin) / 2;

    // [begin, mid] [mid + 1, end] - 分割
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    // [begin, mid] [mid + 1, end] - 合并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;

    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
            tmp[index++] = a[begin1++];
        else
            tmp[index++] = a[begin2++];
    }

    while(begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while(begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }

    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}



int main()
{
    int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    PrintArray(array, 10);

    MergeSort(array, 10);

    PrintArray(array, 10);

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>

using namespace std;


void PrintArray(int* array, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << array[i] << " ";
    }

    cout << endl;
}



// void _MergeSort(int* a, int left, int right, int* tmp)
// {
//     if(left >= right)
//     {
//         return;
//     }

//     int mid = left + (right - left) / 2;

//     // [left, mid] [mid + 1. right] - 分割
//     _MergeSort(a, left, mid, tmp);
//     _MergeSort(a, mid + 1, right, tmp);

//     // [left, mid] [mid + 1, right] - 归并
//     int begin1 = left, end1 = mid;
//     int begin2 = mid + 1, end2 = right;
//     int index = left;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++]; 
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
// }


// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);
//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, end] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp数组中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid][mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp中的数据拷贝回原数组中
//     memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     // 将tmp数组中的数据拷贝回原数组
//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }

//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }


// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//             tmp[index++] = a[begin1++];
//         else
//             tmp[index++] = a[begin2++];
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//         return;

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//             tmp[index++] = a[begin1++];
//         else
//             tmp[index++] = a[begin2++];
//     }

//     while(begin1 <= end1)
//         tmp[index++] = a[begin1++];
//     while(begin2 <= end2)
//         tmp[index++] = a[begin2++];

//     // 将tmp数组中的数据拷贝回tmp数组中
//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }


// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }




// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//         return;

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else 
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//     {
//         return;
//     }

//     int mid = begin + (end - begin) / 2;

//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//             tmp[index++] = a[begin1++];
//         else
//             tmp[index++] = a[begin2++];
//     }

//     while(begin1 <= end1)
//         tmp[index++] = a[begin1++];
//     while(begin2 <= end2)
//         tmp[index++] = a[begin2++];

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(n * sizeof(int));
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }



// void _MergeSort(int* a, int begin, int end, int* tmp)
// {
//     if(begin >= end)
//         return;

//     int mid = begin + (end - begin) / 2;

//     // [begin, mid] [mid + 1, end] - 分割
//     _MergeSort(a, begin, mid, tmp);
//     _MergeSort(a, mid + 1, end, tmp);

//     // [begin, mid] [mid + 1, end] - 合并
//     int begin1 = begin, end1 = mid;
//     int begin2 = mid + 1, end2 = end;
//     int index = begin;

//     while(begin1 <= end1 && begin2 <= end2)
//     {
//         if(a[begin1] < a[begin2])
//         {
//             tmp[index++] = a[begin1++];
//         }
//         else 
//         {
//             tmp[index++] = a[begin2++];
//         }
//     }

//     while(begin1 <= end1)
//     {
//         tmp[index++] = a[begin1++];
//     }
//     while(begin2 <= end2)
//     {
//         tmp[index++] = a[begin2++];
//     }

//     memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
// }

// void MergeSort(int* a, int n)
// {
//     int* tmp = (int*)malloc(sizeof(int) * n);
//     assert(tmp);

//     _MergeSort(a, 0, n - 1, tmp);
//     free(tmp);
// }


void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if(begin >= end)
    {
        return;
    }

    int mid = begin + (end - begin) / 2;

    // [begin, mid] [mid + 1, end] - 分割
    _MergeSort(a, begin, mid, tmp);
    _MergeSort(a, mid + 1, end, tmp);

    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;

    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }

    while(begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while(begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }

    memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}


void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);

    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}


int main()
{
    int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    PrintArray(array, 10);

    MergeSort(array, 10);

    PrintArray(array, 10);

    return 0;
}



